package com.atues.backtrack.nQueue;

import java.util.ArrayList;
import java.util.List;

class Solution {

    List<List<String>> res = new ArrayList<>();
    List<String> path ;

    public List<List<String>> solveNQueens(int n) {
        path = new ArrayList<>(n);
        StringBuilder sb = new StringBuilder();
        while (sb.length() < n)
            sb.append('.');
        for (int i = 0; i < n; i++) {
            path.add(sb.toString());
        }
        backtracking(n, 0);

        return res;
    }

    public void backtracking(int n, int row) {
        if (row == n) {
            res.add(new ArrayList<>(path));
            return;
        }
        StringBuilder sb = new StringBuilder(path.get(row));
        for (int i = 0; i < n; i++) {
            if (sb.charAt(i)=='.' && isValid(row,i,path,n)) {
                sb.replace(i, i + 1, "Q");
                path.set(row, sb.toString());
                backtracking(n, row + 1);
                sb.replace(i, i + 1, "."); // 恢复状态
                path.set(row,sb.toString());

            }
        }
    }

    private boolean isValid(int i, int j, List<String> path,int n) {
        //行、列、斜
//        String s = path.get(i);
//        if( s.indexOf('Q') != -1 )return false;这里应该不会出现，可以剪枝，因为一行只会填充这一个位置
        for (int k = 0; k < n; k++) {
            if(path.get(k).charAt(j) == 'Q')return false;
        }
//        左上
        int startX = j,startY = i;
        while(i >=0 & j >= 0){
            if(path.get(i).charAt(j) == 'Q')return false;
            else {
                i--;j--;
            }
        }
//        右下
        i = startY + 1;
        j = startX + 1;
        while(i < n & j < n){
            if(path.get(i).charAt(j) == 'Q')return false;
            else {
                i++;j++;
            }
        }
//        左下
        i = startY + 1;
        j = startX - 1;
        while(i < n & j >= 0){
            if(path.get(i).charAt(j) == 'Q')return false;
            else {
                i++;j--;
            }
        }
//右上
        i = startY - 1;
        j = startX + 1;
        while(i >= 0 & j < n){
            if(path.get(i).charAt(j) == 'Q')return false;
            else {
                i--;j++;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<String>> lists = solution.solveNQueens(4);
        System.out.println(lists);

    }
}